/**
 * 图的深度优先搜索
 *
 * 2018年 12月 12日 星期三
 * @author fireway
 */
class Vertex {
    public char mLabel;

    public boolean mWasVisited;

    public Vertex(char lab) {
        mLabel = lab;
        mWasVisited = false;
    }
}

class StackX {
    private final int SIZE = 20;
    private int[] mSt;
    private int mTop;

    public StackX() {
        mSt = new int[SIZE];
        mTop = -1;
    }

    public void push(int v) {
        mSt[++mTop] = v;
    }

    public int pop() {
        return mSt[mTop--];
    }

    public int peek() {
        return mSt[mTop];
    }

    public boolean isEmpty() {
        return (mTop == -1);
    }
}

/**
 * 无向图
 */
class Graph {
    private final int MAX_VERTS = 20;
    // 顶点对象放在数组中维护
    private Vertex[] mVertexList;
    private int[][] mAdjMat;
    // 当前顶点的个数
    private int mVertNum;

    private StackX mStackX;

    public Graph() {
        mVertNum = 0;
        mVertexList = new Vertex[MAX_VERTS];
        // adjacency matrix - 邻接矩阵
        mAdjMat = new int[MAX_VERTS][MAX_VERTS];
        for (int i = 0; i < MAX_VERTS; i++) {
            for (int j = 0; j < MAX_VERTS; j++) {
                mAdjMat[i][j] = 0;
            }
        }

        mStackX = new StackX();
    }

    /**
     * 添加顶点
     */
    public void addVertex(char lab) {
        mVertexList[mVertNum++] = new Vertex(lab);
    }

    /**
     * 添加边
     */
    public void addEdge(int start, int end) {
        mAdjMat[start][end] = 1;
        mAdjMat[end][start] = 1;
    }

    /**
     * 显示顶点
     * @param v
     */
    public void displayVertex(int v) {
        System.out.print(mVertexList[v].mLabel);
    }

    /**
     * <p>
     * 深度优先搜索的关键在于能够找到与某一个顶点邻接且没有访问过的顶点
     * </p>
     * <p>
     * 如何做到呢？
     * </p>
     * <p>
     * 邻接矩阵是关键，找到指定顶点所在的行，从第一列开始向后寻找值为1的列； 列号是相邻顶点的号码。
     * 检查这个顶点是否被访问过，如果访问过，那么就访问下一个顶点。
     * </p>
     *
     * @param i
     * @return
     */
    public int getAdjUnvisitedVertex(int j) {
        for (int i = 0; i < mVertNum; i++) {
            if (mAdjMat[j][i] == 1 && !mVertexList[i].mWasVisited) {
                return i;
            }
        }
        return -1;
    }

    /**
     * depth-first search 深度优先算法
     */
    public void dfs() {
        displayVertex(0);
        mStackX.push(0);
        mVertexList[0].mWasVisited = true;

        while (!mStackX.isEmpty()) {
            int j = getAdjUnvisitedVertex(mStackX.peek());
            if (j == -1) {
                mStackX.pop();
            } else {
                displayVertex(j);
                mStackX.push(j);
                mVertexList[j].mWasVisited = true;
            }
        }

        // 在dfs()方法的最后，重置了所有mWasVisited标记位，这样就可以在稍后继续使用dfs()方法
        // 栈此时为空，所以不需要重置。
        for (int j = 0; j < mVertNum; j++) {
            mVertexList[j].mWasVisited = false;
        }
    }

    /**
     * depth-first search 深度优先算法
     */
    public void dfs(int i) {
        displayVertex(i);
        mStackX.push(i);
        mVertexList[i].mWasVisited = true;

        while (!mStackX.isEmpty()) {
            int j = getAdjUnvisitedVertex(mStackX.peek());
            if (j == -1) {
                mStackX.pop();
            } else {
                displayVertex(j);
                mStackX.push(j);
                mVertexList[j].mWasVisited = true;
            }
        }

        // 在dfs()方法的最后，重置了所有mWasVisited标记位，这样就可以在稍后继续使用dfs()方法
        // 栈此时为空，所以不需要重置。
        for (int j = 0; j < mVertNum; j++) {
            mVertexList[j].mWasVisited = false;
        }
    }
}

